The transmission of electronic data via facsimile machines and similar devices has become quite common. Efforts to transmit significantly larger volumes of this data within a substantially shortened period of time are constantly being made. This is true not only to allow data to be sent from one location to another at faster speeds and to cause less inconvenience to the user, but to enable more complex data to be transmitted between the same locations without drastically increasing the required transmission time. For example the facsimile transmission time for a detailed halftoned image will be many times more than that of a simple sheet of black text on a white page when using the same fax machine. By the same token, fax transmission of a color image will require an even greater amount of time than its greatly detailed halftoned counterpart. It is desirable to be able to transmit documents that contain these types of data--as well as others--within a short period of time.
Without any form of data reduction, transmission of color image data files via facsimile would require extensive resources--very fast modems and/or large buffers--and would still take a great deal of time. This would cause transmission of these large data files to become very expensive and therefore, impractical. Instead, the transmission of color image data via fax is typically accomplished using some form of data compression prior to transmission.
The JPEG (Joint Photographic Experts Group) standard provides a well known method of compressing electronic data. JPEG uses the discrete cosine transform (DCT) to map space data into spatial frequency domain data. Simply put, the first step in JPEG compression is to transform an 8.times.8 block of pixels into a set of 8.times.8 coefficients using the DCT. The DCT with the lowest frequency is referred to as the DC coefficient (DCC), and the remaining coefficients are AC coefficients (ACCs). The DCC and ACCs are quantized--divided by an integer referred to as the "step size" and rounded to the nearest whole number. The losses that occur during JPEG compression typically occur during the quantization step. The magnitude of this loss is obviously dependent upon the step size selected and the resulting amount of roundoff required to perform quantization.
Next, the quantized coefficients are arranged in a one dimensional vector by following a selected path (i.e. zigzag) through the 8.times.8 block of quantized coefficients. The DCC is typically the first value in the vector. Ordinary JPEG compression typically includes replacing the quantized DCC with the difference of its actual value minus the DCC of the previous block, to provide a differential DCC. Finally, the vector is encoded into a bit stream through a sequence of Run Length Counting (RLC) operations, combined with Variable Length Codes (VLC) to produce a compressed data stream.
Fax transmission of color image data is often accomplished by scanning the image at the sending fax to generate digital color image data, subjecting this digital color image data to JPEG compression and then transmitting the compressed digital color image data over telephone lines to the receiving fax. Since color image data is so complex, high compression ratios must usually be applied in order to complete transmission of a JPEG compressed file within an acceptable time frame. High compression ratios lead to more data loss, typically at the higher end of the frequency range. Further, the imaging devices typically included with fax machines in the lower end of the market usually include thermal ink-jet printers and would likely use error diffusion halftoning techniques. The halftoning that occurs when using a thermal ink jet printer results in an additional loss of high frequency data. Thus, much of the detail in the original image that is preserved and transmitted will never actually be viewed by the ultimate user.
The "sending" portion of fax transmission includes scanning the original image, generating a corresponding digital image, and reducing the data using any one of a number of techniques, one of which is JPEG compression described above. Once these steps are completed, the compressed data is transmitted serially to the receiving fax in a bit stream. The length of the bit stream used to describe the image is inversely proportional to the amount of compression that has been applied. Thus, if the compression ratio is large the length of the bit stream used to describe the image will be very short, resulting in a substantial reduction in the transmission time for the data stream.
With this in mind, successful fax transmission requires a proper correspondence between the compression ratio being applied to the image and the clock speed of CPU of the sending fax. In other words, if the compression ratio is smaller than necessary for a given CPU speed the data will have to wait to be transmitted, and an appropriately sized buffer will be required. On the other hand, if the compression ratio is high relative to the CPU speed the data will be compressed so much that the modem will become idle waiting for the CPU to complete image processing for the few bits that remain after compression. Since modems are typically configured to detect a large lapse in data transmission as the end of transmission, this large gap typically causes them to disconnect.
Thus, it is advantageous to continue the stream of data from the sending fax to the receiving fax, and eliminate gaps in the data stream. One way to do this is obviously to implement a faster JPEG compressor which can keep the data moving through the modem even if a high compression ratio is used. However, this solution results in significant cost increases and is often impractical. Thus, it is advantageous to provide a continuous stream of data during transmission of a color facsimile by transmitting stored data that emulates that produced by JPEG compression. This eliminates the need for actually performing JPEG compression, which as indicated above, can be a relatively time consuming task when large volumes of data are being processed.
In the present invention, blocks of data similar to those which would be produced by JPEG are stored in advance. The scanned image is then analyzed to assess its content, and the blocks that are similar to those that would be produced during JPEG compression of the image being processed are identified. The identified blocks are then retrieved from storage and transmitted to the receiving device instead of actual JPEG compressed original data. This means that full JPEG compression will not have to take place, and the amount of image processing time can be dramatically reduced.
All pixels, and therefore blocks of pixels, are defined using a certain number of bits. In an image processing operation known as vector quantization (VQ), a block of X.times.Y pixels is mapped to a single "codeword" which is defined using a smaller number of bits than the number required by the original block. Hierarchical Vector Quantization (HVQ) is used in the present invention to analyze the scanned image and select the most closely matching data block. HVQ block matching searches are performed two samples at a time. Thus, look up tables (LUTs) can be used directly to perform HVQ in two or more levels. In the first level, two image pixels are mapped to one codeword, reducing the number of samples by a factor of 2. In the next level, the process is repeated to map pairs of codewords to single codewords. As the process continues, the resulting codewords are mapped to larger and larger amounts of data. The codeword to which each pixel block is ultimately mapped is that associated with image data that most closely matches the image data in the original block of pixels.
The following disclosures may be relevant to aspects of the present invention:
U.S. Pat. No. 5,745,251 to Yamagami issued Apr. 28, 1998 relates to a video signal recording apparatus for recording a video signal in such a manner that the video signal is compressed before it is recorded. The apparatus includes a first coding device for coding input image data into code data having a variable length; a second coding device for coding code data having the variable length and coded by the first coding device into code data having a fixed length; and a memory for storing code data coded by the first coding device.
U.S. Pat. No. 5,699,457 to Adar et al. issued Dec. 16, 1997 discloses a method of bit rate control and block allocation for discrete cosine transform (DCT) image signal compression includes the steps of (a) partitioning the image signals in blocks representing portions of the total image, (b) calculating DCT coefficients for image data in all blocks, (c) obtaining a measure of block activity (BACT) for each block based on DCT coefficients and for the total image activity (ACT) as a sum of the measures of all block activity, and (d) determining a code allocation factor (AF) for each block based on the ratio of block activity (BACT) to target code volume (TCV data) for the coded image data. The method also includes (e) allocating bits for each block using the allocation factor (AF) for each block and the target code volume (DCV data).
U.S. Pat. No. 5,699,170 to Yokose et al. issued Dec. 16, 1997 discloses an image communication system wherein transmission of an image between an image transmission apparatus and an image reception apparatus which include image output sections having different performances can be performed without making an inquiry for the performance prior to transmission. An image is inputted by an image input section and sent to a hierarchization section in the image transmission apparatus. The hierarchization section converts the inputted image into hierarchic communication data and transmits hierarchized data to a selection section of the image reception apparatus. The selection section extracts only necessary data from the hierarchic communication data transmitted thereto in accordance with the performance of an image output section of the image reception section and then sends the necessary data to the image output section after, if necessary, they are converted into image data. The image output section visualize the image data transmitted thereto from the selection section.
U.S. Pat. No. 5,642,438 to Babkin issued Jun. 24, 1997 discloses image compression implementing a fast two-dimensional discrete cosine transform. More specifically, Babkin discloses a method and apparatus for the realization of two-dimensional discrete cosine transform (DCT) for an 8.times.8 image fragment with three levels of approximation of DCT coefficients.
U.S. Pat. No. 5,341,441 to Maeda et al. issued Aug. 23, 1994 discloses method and apparatus for coding image information, and a method of creating code books. A coding apparatus divides digital image information into pixel blocks each having a size of M.times.N pixels, and subjects the image information to vector quantization in block units. The pixel blocks are orthogonally transformed and the characteristics and sequency components of the pixel blocks are detected. Each pixel block is divided into a plurality of sub-blocks in conformity with the detected sequency components. Respective ones of the plurality of divided and outputted sub-blocks are scalar-quantized into sub-vectors of a predetermined number of bits in conformity with the characteristics of the pixel blocks. Respective ones of the scalar-quantized values of the quantized sub-blocks are vector-quantized in conformity with the characteristics of the pixel blocks, these vector-quantized reproduction vector codes are combined and the result is subjected to further vector quantization.
Pending U.S. Ser. No. 09/075935 filed on May 12, 1998 by Ricardo L. DeQueiroz and assigned to the assignee of the present invention discloses an encoding and/or decoding method and apparatus which incorporates decoding commands into a compressed file. The decoding commands are instructions carried along to a decompressor and implement processing performed in the compressed domain. Then, the decompressor processes the data while decompressing it. This reduces the computation time for imaging operations.
Pending U.S. Ser. No. 09/119023 filed on Jul. 20, 1998 by Ricardo L. DeQueiroz entitled Improved Method of Compressing JPEG Files and assigned to the assignee of the present application discloses a method and apparatus for compressing digital image data to improve the efficiency of serial data transmission. The invention accomplishes image compression by performing the most complex portions of a standard compression technique on a smaller amount of data than the usual 8.times.8 block of image data. The invention includes a fast JPEG compressor based on a modified two-dimensional discrete cosine transform.
Pending patent application by Ricardo L. DeQueiroz entitled Method and Apparatus for Analyzing Image Data to Use Multiple Transforms for Enhanced Image Data Transmission and assigned to the assignee of the present invention discloses a method and apparatus for compressing digital image data to improve the efficiency of serial data transmission is disclosed. More specifically, the present invention accomplishes image transmission by providing multiple image processing modules, and then selecting the module that will process the entire in the most efficient manner, based upon the content of the data contained in the image. Image content is analyzed using hierarchical vector quantization.
Pennebaker and Mitchel, "JPEG: Still Image Compression Standard" published by Van Nostrand-Reinhold, 1993 describes in detail the operation of the JPEG standard algorithm for compression of images.
Gersho and Gray, "Vector Quantization and Signal Compression" published by Kluwer Academic, 1992 describes in detail forms of operation of systems based on vector quantization for image compression.
Viswanath and Chou, "An Efficient Algorithm for Hierarchical Compression of Video", in the Proceedings of IEEE International Conference on Image Processing, 1995, pages 275-279, describes the method of hierarchical vector quantization for the compression of image and video.
All of the references cited herein are incorporated by reference for their teachings.
Accordingly, although known apparatus and processes are suitable for their intended purposes, a need remains for . . . thereby improving the efficiency of serial data transmission.